# !/usr/bin/python
# -*- coding: utf-8 -*-

"""
@contact: 微信 1257309054
@file: merge.py
@time: 2022/7/25 21:39
@author: LDC
"""
'''
8、归并排序
先分开再合并，分开成单个元素，合并的时候按照正确顺序合并。
分：
假如我们有一个n个数的数列，下标从0到n-1
　　首先是分开的过程
1 我们按照 n//2 把这个数列分成两个小的数列
2 把两个小数列 再按照新长度的一半 把每个小数列都分成两个更小的
    ...一直这样重复，一直到每一个数分开了
并：
两个有序数组排序的方法则非常简单，同时对两个数组的第一个位置进行比大小，将小的放入一个空数组，然后被放入空数组的那个位置的指针往后 移一个，然后继续和另外一个数组的上一个位置进行比较，以此类推。到最后任何一个数组先出栈完，就将另外一个数组里的所有元素追加到新数组后面。

由于递归拆分的时间复杂度是logN 然而，进行两个有序数组排序的方法复杂度是N，该算法的时间复杂度是N*logN 所以是NlogN。
'''

import random
import time


def merge(left, right):
    # 从两个有顺序的列表里边依次取数据比较后放入result
    # 每次我们分别拿出两个列表中最小的数比较，把较小的放入result
    result = []
    while len(left) > 0 and len(right) > 0:
        # 为了保持稳定性，当遇到相等的时候优先把左侧的数放进结果列表，因为left本来也是大数列中比较靠左的
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    # while循环出来之后 说明其中一个数组没有数据了，我们把另一个数组添加到结果数组后面
    result += left
    result += right
    return result


def mergeSort(li):
    # 不断递归调用自己一直到拆分成成单个元素的时候就返回这个元素，不再拆分了
    if len(li) == 1:
        return li

    # 取拆分的中间位置
    mid = len(li) // 2
    # 拆分过后左右两侧子串
    left = li[:mid]
    right = li[mid:]

    # 对拆分过后的左右再拆分 一直到只有一个元素为止
    # 最后一次递归时候ll和lr都会接到一个元素的列表
    # 最后一次递归之前的ll和rl会接收到排好序的子序列
    ll = mergeSort(left)
    rl = mergeSort(right)

    # 我们对返回的两个拆分结果进行排序后合并再返回正确顺序的子列表
    # 这里我们调用拎一个函数帮助我们按顺序合并ll和lr
    return merge(ll, rl)


if __name__ == '__main__':
    list1 = [random.randint(1, 999) for i in range(10000)]
    list11 = list1.copy()
    start1 = time.perf_counter()
    list2 = mergeSort(list1)
    end1 = time.perf_counter()
    print("归并排序      ", end1 - start1)

    start2 = time.perf_counter()
    list4 = sorted(list11)
    end2 = time.perf_counter()
    print("函数sorted排序", end2 - start2)
    print("排序结果", list2 == list4)
